// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// //自定义类型
// typedef int ElemData;
//
// //自定义树节点
// typedef struct TreeNode {
//     ElemData data;
//     struct TreeNode* left;
//     struct TreeNode* right;
// }TreeNode;
//
// //栈节点
// typedef struct StackNode {
//     TreeNode* data;
//     struct StackNode* next;
// }StackNode;
//
// //栈结构
// typedef struct Stack {
//     StackNode* top;
// }Stack;
//
// //队列节点
// typedef struct QueueNode {
//     TreeNode* data;
//     struct QueueNode* next;
// }QueueNode;
//
// //队列结构
// typedef struct Queue {
//      QueueNode* front;
//      QueueNode* rear;
// }Queue;
//
// //初始化栈
// void InitStack(Stack* s) {
//     s->top=NULL;
// }
//
// //创建树节点
// TreeNode* CreateTreeNode(ElemData x) {
//     TreeNode* newNode=(TreeNode*)malloc(sizeof(TreeNode));
//     if(newNode==NULL) {
//         exit(1);
//     }
//     newNode->data=x;
//     newNode->left=newNode->right=NULL;
//     return newNode;
// }
//
// //插入树节点(二叉搜索树规则:注意)
// TreeNode* InsertTreeNode(TreeNode* root,ElemData x) {
//     if(root==NULL) {
//         return CreateTreeNode(x);
//     }
//     if(x<root->data) {
//         root->left=InsertTreeNode(root->left,x);
//     }else {
//         root->right=InsertTreeNode(root->right,x);
//     }
//     return root;
// }
//
// //非递归使用栈(入栈)
// void push(Stack* s,TreeNode* node){
//     StackNode* newNode=(StackNode*)malloc(sizeof(StackNode));
//     newNode->data=node;
//     newNode->next=s->top;
//     s->top=newNode;
// }
//
// //非递归使用栈(出栈)
// TreeNode* pop(Stack* s) {
//     StackNode* tmp=s->top;
//     s->top=s->top->next;
//     TreeNode* node=tmp->data;
//     free(tmp);
//     return node;
// }
//
// //先序(递归)
// void preOrder(TreeNode* root) {
//     if(root) {
//         printf("%d ",root->data);
//         preOrder(root->left);
//         preOrder(root->right);
//     }
// }
//
// //先序(非递归)
// void preOrderNonRecursive(TreeNode* root) {
//     Stack s;
//     InitStack(&s);
//     TreeNode* p=root;
//     while (p||s.top!=NULL) {
//         if(p) {
//             printf("%d ",p->data);
//             push(&s,p);
//             p=p->left;
//         }else {
//             p=pop(&s);
//             p=p->right;
//         }
//     }
// }
//
// //中序(递归)
// void inOrder(TreeNode* root) {
//     if(root) {
//         inOrder(root->left);
//         printf("%d ",root->data);
//         inOrder(root->right);
//     }
// }
//
// //中序(非递归)
// void inOrderNonRecursive(TreeNode* root) {
//     Stack s;
//     InitStack(&s);
//     TreeNode* p=root;
//     while (p||s.top!=NULL) {
//         if(p) {
//             push(&s,p);
//             p=p->left;
//         }else {
//             p=pop(&s);
//             printf("%d ",p->data);
//             p=p->right;
//         }
//     }
// }
//
// //后序(递归)
// void postOrder(TreeNode* root) {
//     if(root) {
//         postOrder(root->left);
//         postOrder(root->right);
//         printf("%d ",root->data);
//     }
// }
//
// //后序(非递归:注意)
// //1.循环结束条件:p空且栈空
// //2.p不空,入栈,p到左孩子
// //3·p空,取栈顶,看看右孩子
// //  没有右孩子或者右孩子访问过,出栈标记,否则p到右孩子
// void postOrderNonRecursive(TreeNode* root) {
//     Stack s;
//     InitStack(&s);
//     TreeNode* p=root;
//     TreeNode* r=NULL;
//     while (p||s.top!=NULL) {
//         if(p) {
//             push(&s,p);
//             p=p->left;
//         }else {
//             p=s.top->data;
//             if(p->right==NULL||p->right==r) {
//                 p=pop(&s);
//                 printf("%d ",p->data);
//                 r=p;
//                 p=NULL;
//             }else {
//                 p=p->right;
//             }
//         }
//     }
// }
//
// //入队操作(层次遍历)
// void enqueue(Queue* q, TreeNode* node) {
//     QueueNode* newNode=(QueueNode*)malloc(sizeof(QueueNode));
//     if(newNode==NULL) {
//         printf("申请失败\n");
//         exit(1);
//     }
//     newNode->data=node;
//     newNode->next=NULL;
//     if(q->rear==NULL) {
//         q->front=q->rear=newNode;
//     }
//     q->rear->next=newNode;
//     q->rear=newNode;
// }
//
// //出队操作(层次遍历)
// TreeNode* dequeue(Queue* q) {
//     if(q->front==NULL) {
//         return NULL;
//     }
//     QueueNode* tmp=q->front;
//     TreeNode* node=tmp->data;
//     q->front=q->front->next;
//     if(q->front==NULL) {
//         q->rear=NULL;
//     }
//     free(tmp);
//     return node;
// }
//
// //当前队列元素个数
// int Count(Queue* q) {
//     int count=0;
//     QueueNode* p=q->front;
//     while (p!=q->rear) {
//         count++;
//         p=p->next;
//     }
//     return count;
// }
//
// //层次遍历(注意)
// void levelOrder(TreeNode* root) {
//     Queue q;
//     q.front=q.rear=NULL;
//     enqueue(&q,root);
//     while (q.front) {
//         TreeNode* node=dequeue(&q);
//         printf("%d ",node->data);
//         if(node->left) {
//             enqueue(&q,node->left);
//         }
//         if(node->right) {
//             enqueue(&q,node->right);
//         }
//     }
// }
//
// // 查找
// bool search(TreeNode* root, int key) {
//     if(root==NULL) {
//         return false;
//     }
//     if(root->data==key) {
//         return true;
//     }else if(key<root->data) {
//             return  search(root->left,key);
//     }else {
//             return  search(root->right,key);
//     }
// }
//
// // 释放二叉树
// void freeTree(TreeNode* root){
//     if(root){
//         freeTree(root->left);
//         freeTree(root->right);
//         free(root);
//     }
// }
//
// //测试开始
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int n = sizeof(values) / sizeof(values[0]);
//     for(int i=0;i<n;i++) {
//         root=InsertTreeNode(root,values[i]);
//     }
//     printf("递归先序:");preOrder(root);printf("\n");
//     printf("非递归先序:");preOrderNonRecursive(root);printf("\n");
//     printf("递归中序:");inOrder(root);printf("\n");
//     printf("非递归中序:");inOrderNonRecursive(root);printf("\n");
//     printf("递归后序:");postOrder(root);printf("\n");
//     printf("非递归后序:");postOrderNonRecursive(root);printf("\n");
//     printf("层次遍历:");levelOrder(root);printf("\n");
//     printf("查找:");int i=search(root,100);i==1?printf("存在"):printf("不存在");
//     freeTree(root);
//     return 0;
// }